package Demo3;

import java.util.Scanner;

public class CircularLinkedList {
    static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    // 删除结点 s 的直接前驱结点
    public static Node deletePriorNode(Node s) {
        if (s == null || s.next == s) {
            return s; // 如果链表为空或只有一个节点，直接返回
        }

        Node cur = s;
        Node prev = null;

        // 循环遍历找到 s 的前驱节点
        while (cur.next != s) { // 遍历直到找到 s 的前一个节点
            prev = cur;
            cur = cur.next;
        }

        // cur.next == s, 此时 cur 是 s 的前驱节点，执行删除操作
        if (prev != null) {
            prev.next = s; // 跳过 cur，prev 的 next 指向 s
        }

        // 如果只有两个节点的情况
        if (cur == s) {
            s.next = s; // 更新链表为只包含 s 自己的循环链表
        }

        return s; // 返回指向当前节点 s
    }

    // 打印循环链表中的所有节点，从指定节点开始
    public static void printCircularList(Node s) {
        if (s == null) return;

        Node cur = s;
        do {
            System.out.print(cur.value + " ");
            cur = cur.next;
        } while (cur != s); // 循环遍历链表

        System.out.println();
    }

    // 创建单循环链表，返回某个节点（作为起点）
    public static Node createCircularList(int[] values) {
        if (values.length == 0) return null;

        Node head = new Node(values[0]);
        Node tail = head;
        for (int i = 1; i < values.length; i++) {
            Node newNode = new Node(values[i]);
            tail.next = newNode;
            tail = newNode;
        }
        tail.next = head; // 构成循环链表
        return head; // 返回某个节点（这里是头节点）
    }

    public static Node findAndDeletePrior(Node s, int target) {
        if (s == null) {
            System.out.println("链表为空");
            return null;
        }

        Node cur = s;

        // 从当前节点 s 开始查找 target，找到后删除其前驱节点
        do {
            if (cur.value == target) {
                s = deletePriorNode(cur); // 删除前驱节点
                System.out.println("删除了值为 " + target + " 的前驱节点");
                return s; // 返回操作后的链表
            }
            cur = cur.next;
        } while (cur != s); // 循环遍历整个链表

        System.out.println("未找到目标值 " + target);
        return s; // 如果没找到目标值，返回原链表
    }

    public static void main(String[] args) {
        // 初始化链表
        int[] values = {1, 2, 3, 4, 5};
        Node s = createCircularList(values);

        System.out.println("初始循环链表:");
        printCircularList(s);

        // 用户输入要删除前驱节点的目标值
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入要删除前驱节点的值: ");
        int target = scanner.nextInt();

        // 调用 findAndDeletePrior 函数查找并删除前驱节点
        s = findAndDeletePrior(s, target);

        System.out.println("删除前驱节点后的循环链表:");
        printCircularList(s);

        scanner.close();
    }
}
